Handling of Numeric Ranges for Graph%2DBased Knowledge Discovery.

Using a Graph%2DBased Approach for Discovering Cybercrime.

Mining for insider threats in business transactions and processes.

Empirical comparison of graph classification algorithms.

Faster computation of the direct product kernel for graph classification.

Discovering Anomalies to Multiple Normative Patterns in Structural and Numeric Data.

gRegress Extracting Features from Graph Transactions for Regression.
In this work we propose gRegress, a new algorithm which given set a of labeled graphs and a real value associated with each graph extracts the complete set of subgraphs such that a) each subgraph in this set has correlation with the real value above a userspecified threshold and b) each subgraph in this set has correlation with any other subgraph in the set below a user-specified threshold. gRegress incorporates novel pruning mechanisms based on correlation of a subgraph feature with the output and correlation with other subgraph features. These pruning mechanisms lead to significant speedup. Experimental results indicate that in terms of runtime, gRegress substantially outperforms gSpan, often by an order of magnitude while the regression models produced by both approaches have comparable accuracy. 1
Applying graph%2Dbased anomaly detection approaches to the discovery of insider threats.

Learning patterns in the dynamics of biological networks.

Substructure Analysis of Metabolic Pathways by Graph%2DBased Relational Learning.

Dynamic Graph%2Dbased Relational Learning of Temporal Patterns in Biological Networks Changing over Time.

Temporal and structural analysis of biological networks in combination with microarray data.

Graph%2DBased Data Mining in Dynamic Networks Empirical Comparison of Compression%2DBased and Frequency%2DBased Subgraph Mining.

Game%2DBased Simulation for the Evaluation of Threat Detection in a Seaport Environment.

Strategic Path Planning on the Basis of Risk vs. Time.

Inferring Graph Grammars by Detecting Overlap in Frequent Subgraphs.

Inference of Edge Replacement Graph Grammars.

Report on the First International Workshop on Mining Graphs and Complex Structures %28MGCS%2707%29.

Learning Node Replacement Graph Grammars in Metabolic Pathways.

Mining for Structural Anomalies in Graph%2Dbased Data.
In this paper we present graph-based approaches to mining for anomalies in domains where the anomalies consist of unexpected entity/relationship alterations that closely resemble non-anomalous behavior. We introduce three novel algorithms for the purpose of detecting anomalies in all possible types of graph changes. Each of our algorithms focuses on a specific graph change and uses the minimum description length principle to discover those substructure instances that contain anomalous entities and relationships. Using synthetic and real-world data, we evaluate the effectiveness of each of these algorithms in terms of each of the types of anomalies. Each of these algorithms demonstrates the usefulness of examining a graph-based representation of data for the purposes of detecting fraud.
Inference of Edge Replacement Graph Grammars.

Discovering Structural Anomalies in Graph%2DBased Data.
The ability to mine data represented as a graph has become important in several domains for detecting various structural patterns. One important area of data mining is anomaly detection, particularly for fraud, but less work has been done in terms of detecting anomalies in graph-based data. While there has been some work that has used statistical metrics and conditional entropy measurements, the results have been limited to certain types of anomalies and specific domains. In this paper we present graphbased approaches to uncovering anomalies in domains where the anomalies consist of unexpected entity/relationship deviations that resemble nonanomalous behavior. Using synthetic and real-world data, we evaluate the effectiveness of these algorithms at discovering anomalies in a graph-based representation of data. 1.
Learning from Supervised Graphs.
Graph-based relational learning (GBRL) differs from logicbased relational learning, as addressed by inductive logic programming techniques, and differs from frequent subgraph discovery, as addressed by many graph-based data mining techniques. Learning from graphs, rather than logic, presents representational issues both in input data preparation and output pattern language. While a form of graph-based data mining, GBRL focuses on identifying novel, not necessarily most frequent, patterns in a graph-theoretic representation of data. This approach to graph-based data mining provides both simplifications and challenges over frequency-based approaches. In this paper we discuss these issues and future directions of graph-based relational learning.
Graph%2DBased Analysis of Human Transfer Learning Using a Game Testbed.

Inference of node replacement graph grammars.
Abstract. Graph grammars combine the relational aspect of graphs with the iterative and recursive aspects of string grammars, and thus represent an important next step in our ability to discover knowledge from data. In this paper we describe an approach to learning node replacement graph grammars. This approach is based on previous research in frequent isomorphic subgraphs discovery. We extend the search for frequent subgraphs by checking for overlap among the instances of the subgraphs in the input graph. If subgraphs overlap by one node we propose a node replacement grammar production. We also can infer a hierarchy of productions by compressing portions of a graph described by a production and then infer new productions on the compressed graph. We validate this approach in experiments where we generate graphs from known grammars and measure how well our system infers the original grammar from the generated graph. We also describe results on several real-world tasks from chemical mining to XML schema induction. We briefly discuss other grammar inference systems indicating that our study extends classes of learnable graph grammars.
Anomaly detection in data represented as graphs.

Building Test Beds for AI with the Q3 Mod Base.

Application of Graph%2Dbased Data Mining to Metabolic Pathways.

Graph Grammar Induction on Structural Data for Visual Programming.
Computer programs that can be expressed in two or more dimensions are typically called visual programs. The underlying theories of visual programming languages involve graph grammars. As graph grammars are usually constructed manually, construction can be a time-consuming process that demands technical knowledge. Therefore, a technique for automatically constructing graph grammars—at least in part—is desirable. An induction method is given to infer node replacement graph grammars. The method operates on labeled graphs of broad applicability. It is evaluated by its performance on inferring graph grammars from various structural representations. The correctness of an inferred grammar is verified by parsing graphs not present in the training set. 1.
Classification of Threats Via a Multi%2Dsensor Security Portal.

Detecting Anomalies in Cargo Using Graph Properties.

Inference of Node Replacement Recursive Graph Grammars.
Graph grammars combine the relational aspect of graphs with the iterative and recursive aspects of string grammars, and thus represent an important next step in our ability to discover knowledge from data. In this paper we describe an approach to learning node replacement graph grammars. This approach is based on previous research in frequent isomorphic subgraphs discovery. We extend the search for frequent subgraphs by checking for overlap among the instances of the subgraphs in the input graph. If subgraphs overlap by one node we propose a node replacement grammar production. We also can infer a hierarchy of productions by compressing portions of a graph described by a production and then infer new productions on the compressed graph. We validate this approach in experiments where we generate graphs from known grammars and measure how well our system infers the original grammar from the generated graph. We also describe results on several real-world tasks from chemical mining to XML schema induction. We briefly discuss other grammar inference systems indicating that our study extends classes of learnable graph grammars.
The 2005 International Florida Artificial Intelligence Research Society Conference A Report.

Advances in Knowledge Acquisition and Representation.

Structure Discovery in Sequentially%2Dconnected Data Streams.

A Learning Architecture for Automating the Intelligent Environment.
Developing technologies and systems for perception and perspicacious automated control of home and workplace environments is a challenging problem. We present a complete agent architecture for learning to automate the intelligent environment and discuss the development, deployment, and techniques utilized in our working intelligent environments. Empirical evaluation of our approach has proven its effectiveness at reducing inhabitant interactions by 72.2%.
Structure Discovery in Sequentially Connected Data.

A Serial Partitioning Approach to Scaling Graph%2DBased Knowledge Discovery.

Automated HPOMDP Construction through Data%2Dmining Techniques in the Intelligent Environment Domain.

Learning from Examples in a Single Graph.

Automation Intelligence for the Smart Environment.
Scaling AI algorithms to large problems requires that these algorithms work together to harness their respective strengths. We introduce a method of automatically constructing HHMMs using the output of a sequential data-mining algorithm and sequential prediction algorithm. We present the theory of this technique and demonstrate results using the MavHome intelligent environment. 1
Managing Adaptive Versatile Environments.

Graph%2Dbased Relational Learning with Application to Security.
Abstract. We describe an approach to learning patterns in relational data represented as a graph. The approach, implemented in the Subdue system, searches for patterns that maximally compress the input graph. Subdue can be used for supervised learning, as well as unsupervised pattern discovery and clustering. We apply Subdue in domains related to homeland security and social network analysis. Keywords: Graphs, relational learning, security
Editorial.
calls &amp; calendarEDITORIAL

Current And Future Trends In Feature Selection And Extraction For Classification Problems.


Managing Adaptive Versatile environments.

Comparison of graph%2Dbased and logic%2Dbased multi%2Drelational data mining.
The goal of this paper is to generate insights about the differences between graph-based and logic-based approaches to multi-relational data mining by performing a case study of graph-based system, Subdue and the inductive logic programming system, CProgol. We identify three key factors for comparing graph-based and logic-based multi-relational data mining; namely, the ability to discover structurally large concepts, the ability to discover semantically complicated concepts and the ability to effectively utilize background knowledge. We perform an experimental comparison of Subdue and CProgol on the Mutagenesis domain and various artificially generated Bongard problems. Experimental results indicate that Subdue can significantly outperform CProgol while discovering structurally large multi-relational concepts. It is also observed that CProgol is better at learning semantically complicated concepts and it tends to use background knowledge more effectively than Subdue. 1.
Agent%2Dbased Players for a First%2Dperson Entertainment%2Dbased Real%2Dtime Artificial Environment.

Structure Discovery from Sequential Data.

Attribute%2DValue Selection Based on Minimum Description Length.
We introduce a new method for attribute value  selection, which is driven by the minimum  description length principle. We demonstrate the  viability of the approach on the Wisconsin breast  cancer data set, show a working exa mple and  evaluate the approach against earlier systems.
Structural web search engine.

Mdl%2Dbased context%2Dfree graph grammar induction and applications.

Algorithm and Experiments in Testing Planar Graphs for Isomorphism.

Identifying Inhabitants of an Intelligent Environment Using a Graph%2DBased Data Mining System.
The goal of the MavHome smart home project is to build an intelligent home environment that is aware of its inhabitants and their activities. Such a home is designed to provide maximum comfort to inhabitants at minimum cost. This can be done by learning the activities of the inhabitants and to automate those activities. For this it is necessary to identify among multiple inhabitants who is currently present in the home. Subdue is a graph-based data mining algorithm that discovers patterns in structural data. By representing the activity patterns for each inhabitant as graphs, Subdue can be used for inhabitant identification. We introduce a multiple-class learning version of Subdue and show some preliminary results on synthetic smart home activity data for
Structural Web Search Engine.

Evaluating Human%2DConsistent Behavior in a Real%2Dtime First%2Dperson Entertainment%2Dbased Artificial Environment.

MDL%2DBased Context%2DFree Graph Grammar Induction.
We present an algorithm for the inference of context-free   graph grammars from examples. The algorithm builds on an   earlier system for frequent substructure discovery, and is   biased toward grammars that minimize description length.   Grammar features include recursion, variables and relationships.
Using a Graph%2DBased Data Mining System to Perform Web Search.

Graph%2Dbased relational learning current and future directions.
Graph-based relational learning (GBRL) differs from logicbased relational learning, as addressed by inductive logic programming techniques, and differs from frequent subgraph discovery, as addressed by many graph-based data mining techniques. Learning from graphs, rather than logic, presents representational issues both in input data preparation and output pattern language. While a form of graph-based data mining, GBRL focuses on identifying novel, not necessarily most frequent, patterns in a graph-theoretic representation of data. This approach to graph-based data mining provides both simplifications and challenges over frequency-based approaches. In this paper we discuss these issues and future directions of graph-based relational learning.
Enhancing Structure Discovery for Data Mining in Graphical Databases Using Evolutionary Programming.
The purpose of this paper is to develop an evolutionary programming based system that performs data mining on databases represented as graphs. The importance of such an endeavor can hardly be overemphasized, given that much of the data collected nowadays is structural in nature, or is composed of parts and relations between the parts, which can be naturally represented as graphs. The searching capability of evolutionary programming is utilized for discovering concepts or substructures that are often repeating in such structural data. The superiority of the proposed technique over the previously developed Subdue system (Cook and Holder 2000), which uses a computationally constrained beam search in the space of substructures, is demonstrated for a number of data sets in the Web domain.
Graph%2DBased Relational Concept Learning.
We introduce a graph-based relational concept  learning approach and its implementation in the  SubdueCL system. We start by describing the  Subdue discovery system that uses a graph  representation and was extended to perform the  concept learning task. Then, we present  SubdueCL, our graph-based concept learner.
Experimental Comparison of Graph%2DBased Relational Concept Learning with Inductive Logic Programming Systems.
We compare our graph-based relational concept learning approach  &#034;SubdueCL&#034; with the ILP systems FOIL and Progol. In order to be fair in the  comparison, we use the conceptual graphs representation. Conceptual graphs  have a standard translation from graphs into logic. In this way, we introduce  less bias during the translation process. We experiment with different types of  domains. First, we show our experiments with an artificial domain to describe  how SubdueCL performs with the conceptual graphs representation. Second,  we experiment with several flat and relational domains. The results of the  comparison show that the SubdueCL system is competitive with ILP systems in  both flat and relational domains.
Structural Web Search Using a Graph%2DBased Discovery System.
Accessing information of interest on the Internet presents a challenge to scientists and analysts,  particularly if the desired information is structural in nature. Our goal is to design a structural search  engine which uses the hyperlink structure of the Web, in addition to textual information, to search for  sites of interest. To design a structural search engine, we use the SUBDUE graph-based discovery  tool. The tool, called WebSUBDUE, is enhanced by WordNet features that allow the engine to  search for synonym terms. Our search engine retrieves sites corresponding to structures formed by  graph-based user queries. We demonstrate the approach on a number of structural web queries.
A Client%2DServer Interactive Tool for Integrated Artificial Intelligence Curriculum.
The goal of this project is to increase students&#039; interest in Artificial Intelligence, as well as to promote  learning of the topics that comprise the subject. We describe the development of a web-based  multimedia delivery method to accomplish this goal, and outline plans for continued development of  the tool. The highlight of the course material is an integrated simulation environment that allows  students to develop and test AI algorithms in a dynamic, uncertain, visual environment.
Graph%2DBased Concept Learning.
Introduction  Concept Learning is a Machine Learning technique in which the learning process is driven by providing positive and negative examples to the learner. From those examples, the learner builds a hypothesis (concept) that describes the positive examples and excludes the negative examples. Inductive Logic Programming (ILP) systems have successfully been used as concept learners. Examples of those are Foil [1] and Progol [5]. The main engine of these systems is based in first order logic. In this research we introduce a graph based relational concept learning system called SubdueCL, which through the experiments has shown that it is competitive with ILP systems in different types of domains. SubdueCL is an extension made to the Subdue [2] system, which is an unsupervised graph based learner. The extensions made to Subdue to provide the concept learning capability were mainly related to the ability to accept as input positive and negative examples and the criteria used to
Cover story structural Web search using a graph%2Dbased discovery system.

Graph%2DBased Hierarchical Conceptual Clustering.
Hierarchical conceptual clustering has been proven to be a useful data mining technique. Graph-based representation of structural information has been shown to be successful in knowledge discovery. The Subdue substructure discovery system provides the advantages of both approaches. In this paper we present Subdue and focus on its clustering capabilities. We use two examples to illustrate the validity of the approach both in structured and unstructured domains, as well as compare Subdue to an earlier clustering algorithm.
Graph%2DBased Hierarchical Conceptual Clustering.
Hierarchical conceptual clustering has been proven to be a useful data mining technique. Graph-based representation of structural information has been shown to be successful in knowledge discovery. The Subdue substructure discovery system provides the advantages of both approaches. In this paper we present Subdue and focus on its clustering capabilities. We use two examples to illustrate the validity of the approach both in structured and unstructured domains, as well as compare Subdue to an earlier clustering algorithm.
Graph Based Concept Learning.
Introduction  Concept Learning is a Machine Learning technique in which the learning process is driven by providing positive and negative examples to the learner. From those examples, the learner builds a hypothesis (concept) that describes the positive examples and excludes the negative examples. Inductive Logic Programming (ILP) systems have successfully been used as concept learners. Examples of those are Foil [1] and Progol [5]. The main engine of these systems is based in first order logic. In this research we introduce a graph based relational concept learning system called SubdueCL, which through the experiments has shown that it is competitive with ILP systems in different types of domains. SubdueCL is an extension made to the Subdue [2] system, which is an unsupervised graph based learner. The extensions made to Subdue to provide the concept learning capability were mainly related to the ability to accept as input positive and negative examples and the criteria used to
Graph%2DBased Hierarchical Conceptual Clustering in Structural Databases.
Introduction  Cluster analysis has been studied and developed in many areas for a wide variety of applications. The purpose of applying clustering to a database is to gain better understanding of the data, in many cases through revealing hierarchical topologies. We are working on extending the Subdue structural knowledge discovery system with clustering functionalities. Past works related to ours are an incremental approach called Cobweb [Fisher 1987], and its extension, Labyrinth [Thompson &amp; Langley 1991], that can represent structured objects using a probabilistic model.  Conceptual Clustering Using Subdue  Subdue [Holder and Cook 1993] is a knowledge discovery system that can deal with structured data by working on their graph representation. This includes vertex and edge labels, as well as directed and undirected edges, where objects and data usually map to vertices, and relationships and attributes map to edges.  Subdue&#039;s discovery algorithm discovers interesting, repetitive subst
Discovering Structural Patterns in Telecommunications Data.
With the increasing amount and complexity of data being collected, there is an urgent need  to create automated techniques for mining the data. In particular, data being generated and  stored by telecom companies overwhelms scientists&#039; ability to manually discover patterns in the  data. Because much of this data is structural in nature, or composed of parts and relations  between the parts, linear attribute-value based algorithms will not capture all of the intricacies  of the data. Hence, there exists a need to develop scalable tools to analyze and discover concepts  in structural databases.  1 Introduction  New technology and new laws are changing the telecommunications industry at a blinding rate. New methods of mining the data are needed to understand and control these changes. Because the amount of collected data far exceeds the ability to manually search for and interpret patterns in the data, there is a need to improve the discovery of knowledge in these large databases.  Equipm...
Structural Knowledge Discovery Used to Analyze Earthquake Activity.
The Subdue structural discovery system is being used as the Data Mining tool to study the &amp;quot;Orizaba Fault &amp;quot; located in Mexico, as part of a research project of the geologist Dr. Burke Burkart. We analyze the information of the Earthquake Database to discover if the earthquake activity in the area is related to the fault. We experimented with different samples of data mainly using two heuristics to guide Subdue through the substructure discovery process. We also added some spatio-temporal information as background knowledge. The results show how Subdue can successfully be used as a Data Mining tool in Real World Domains.
Graph%2DBased Hierarchical Conceptual Clustering.
Hierarchical conceptual clustering has been proven to be a useful data mining technique. Graph-based representation of structural information has been shown to be successful in knowledge discovery. The Subdue substructure discovery system provides the advantages of both approaches. In this paper we present Subdue and focus on its clustering capabilities. We use two examples to illustrate the validity of the approach both in structured and unstructured domains, as well as compare Subdue to an earlier clustering algorithm.
Graph%2DBased Data Mining.
With the increasing amount and complexity of today&#039;s data, there is an urgent need to  accelerate data mining of large databases. Furthermore, much of the data is structural in  nature, or is composed of parts and relations between the parts. Hence, there exists a need to  develop scalable tools to analyze and discover concepts in structural databases.  The goal of this research is to provide a system that performs data mining on databases  represented as graphs. In this paper, we demonstrate how the Subdue system can be used to  perform two key techniques for data mining: unsupervised pattern discovery and supervised  concept learning from examples. Applications of the Subdue system to databases representing  CAD circuits and protein molecules as well as to several databases from the UC Irvine repository  will be presented to demonstrate the scalability and eectiveness of the graph-based system.  1 Introduction  The large amount of data collected today is quickly overwhelming researc...
Structural Knowledge Discovery in Chemical and Spatio%2DTemporal Databases.

Applying the Subdue Substructure Discovery System to the Chemical Toxicity Domain.
The ever-increasing number of chemical compounds added every year has not been accompanied by a similar growth in our ability to analyze and classify these compounds. The problem of prevention of cancer caused by many of these chemicals has been of great scientific and humanitarian value. The use of AI discovery tools for predicting chemical toxicity is being investigated. The basic idea behind the work is to obtain structure-activity representation (SARs)[Srinivasan et al.], which relates molecular structures to cancerous activity. The data is obtained from the U.S National Toxicology Program conducted by the National Institute of Environmental Health Sciences (NIEHS). A general approach to automatically discover repetitive substructures from the datasets is outlined by this research. Relevant SARs are identified using the Subdue substructure discovery system that discovers commonly occurring substructures in a given set of compounds. The best substructure given by Subdue is used as a...
Application of Knowledge Discovery to Molecular Biology Identifying Structural Regularities in Proteins.

Discovering Concepts in Structural Data.
Introduction  Automated knowledge discovery is essential for extracting information from databases [2]. However, complex databases have moved from the simplistic attribute-value representation assumed by recent knowledge-discovery systems to a structural data representation that reflects the relationships among objects. Discovering concepts in this structural data requires the identification of common substructures within the data. The motivation for this process is not merely to find substructures capable of compressing the data by abstracting instances of the substructure, but also to identify conceptually interesting substructures that enhance the interpretation of the data. Substructure discovery is the process of identifying concepts describing interesting and repetitive substructures within structural data. Once discovered, the substructure concept can be used to simplify the data by replacing instances of the substructure with a pointer to the newly discovered concept. T
Experimentation%2DDriven Knowledge Acquisition for Planning.
Knowledge engineering for planning is expensive and the resulting knowledge can be imperfect. To autonomously learn a plan operator definition from environmental feedback, our learning system WISER explores an instantiated literal space using a breadth-first search technique. Each node of the search tree represents a state, a unique subset of the instantiated literal space. A state at the root node is called a seed state. WISER can generate seed states with or without utilizing imperfect expert knowledge. WISER experiments with an operator at each node. The positive state, in which an operator can be successfully executed, constitutes initial preconditions of an operator. We analyze the number of required experiments as a function of the number of the missing preconditions in a seed state. We introduce a naive domain assumption to test only a subset of the exponential state space. Since breadth- rst search is expensive, WISER introduces two search techniques to reorder literals at each l...
Knowledge discovery in molecular biology Identifying structural regularities in proteins.
In recent years, there has been an explosive amount of molecular biology information obtained  and deposited in various databases. Identifying and interpreting interesting patterns from this  massive amount of information has become an essential component in directing further molecular  biology research.  The goal of this research is to discover structural regularities in protein sequences by applying  the Subdue discovery system to databases found in the Brookhaven Protein Data Bank. In  this paper we discuss issues relevant to this application including data preparation and representation.  We report on the results of applying Subdue to several classes of protein structures  and discuss the potential signicance of these results to the study of proteins.    Supported by NSF grant ILI-9615272 and THECB grant 003656-045.  1  1 Introduction  The topic of nding biologically meaningful patterns in sequences, secondary, and tertiary (threedimensional) structures of proteins and other mac...
Exploiting Parallelism in a Structural Scientific Discovery System to Improve Scalability.

Coupling Two Complementary Knowledge Discovery Systems.

Exploiting Parallelism in Knowledge Discovery Systems to Improve Scalability.
The large amount of data collected today is quickly overwhelming researchers &#039; abilities to interpret the data and discover interesting patterns. Knowledge discovery and data mining approaches hold the potential to automate the interpretation process, but these approaches frequently utilize computationally expensive algorithms. In particular, scienti�c discovery systems focus on the utilization of richer data representation, sometimes without regard for scalability. This research outlines a general approach for scaling KDD systems using parallel and distributed resources and applies the suggested strategies to the Subdue knowledge discovery system. Subdue has been used to discover interesting and repetitive concepts in graph-based databases from a variety of domains, but requires a substantial amount of processing time. Experiments that demonstrate that scalability of parallel versions of the Subdue system are performed using CAD circuit databases and arti�cially-generated databases, and potential achievements and obstacles are discussed. 1
Improving Scalability in a Scientific Discovery System by Exploiting Parallelism.
The large amount of data collected today is quickly overwhelming researchers&#039; abilities to interpret the data and discover interesting patterns. Knowledge discovery and data mining approaches hold the potential to automate the interpretation process, but these approaches frequently utilize computationally expensive algorithms. This research outlines a general approach for scaling KDD systems using parallel and distributed resources and applies the suggested strategies to the  Subdue knowledge discovery system. Subdue has been used to discover interesting and repetitive concepts in graph-based databases from a variety of domains, but requires a substantial amount of processing time. Experiments that demonstrate scalability of parallel versions of the Subdue system are performed using CAD circuit databases and artificially-generated databases, and potential achievements and obstacles are discussed. Introduction  One of the barriers to the integration of scientific discovery methods into ...
An Emprirical Study of Domain Knowledge and Its Benefits to Substructure Discovery.

User%2DCentered System Decomposition Z%2DBased Requirements Clustering.

Scalable Discovery of Informative Structural Concepts Using Domain Knowledge.
Discovering repetitive, and functional substructures in large structural databases improves the ability to interpret and compress the data. However, scientists working with a database in their area of expertise often search for predetermined types of structures, or for structures exhibiting characteristics specific to the domain. This paper presents a method for guiding the discovery process with domain-specific knowledge. In this paper, the Subdue discovery system is used to evaluate the benefits of using domain knowledge to guide the discovery process. Results show that domain-specific knowledge improves the search for substructures which are useful to the domain, and leads to greater compression of the data. Empirical and theoretical results also indicate the scalability of the algorithm to increasingly large structural databases. Keywords--data mining, minimum description length principle, data compression, inexact graph match, domain knowledge, scalability   Supported by NASA gran...
Decision%2DTheoretic Cooperative Sensor Planning.
This paper describes a decision-theoretic approach to cooperative sensor planning between multiple autonomous vehicles executing a military mission. For this autonomous vehicle application, intelligent cooperative reasoning must be used to select optimal vehicle viewing locations and select optimal camera pan and tilt angles throughout the mission. Decisions are made in such a way as to maximize the value of information gained by the sensors while maintaining vehicle stealth. Because the mission involves multiple vehicles, cooperation can be used to balance the work load and to increase information gain. This paper presents the theoretical foundations of our cooperative sensor planning research and describes the application of these techniques to ARPA&#039;s Unmanned Ground Vehicle program.  1 Introduction  Traditionally, research in multi-agent planning and research in image understanding have been pursued independently. The ARPA Unmanned Ground Vehicle (UGV) program is pulling together th...
Intermediate Decision Trees.
Intermediate decision trees are the subtrees of the full (unpruned) decision tree generated in a breadth-first order. An extensive empirical investigation evaluates the classification error of intermediate decision trees and compares their performance to full and pruned trees. Empirical results were generated using C4.5 with 66 databases from the UCI machine learning database repository. Results show that when attempting to minimize the error of the pruned tree produced by C4.5, the best intermediate tree performs significantly better in 46 of the 66 databases. These and other results question the effectiveness of decision tree pruning strategies and suggest further consideration of the full tree and its intermediates. Also, the results reveal specific properties satisfied by databases in which the intermediate full tree performs best. Such relationships improve guidelines for selecting appropriate inductive strategies based on domain properties. 1 Introduction  Numerous decision tree ...
Substucture Discovery in the SUBDUE System.

Analyzing the Benefits of Domain Knowledge in Substructure Discovery.
Discovering repetitive, interesting, and functional substructures in a structural  database improves the ability to interpret and compress the data. However, scientists  working with a database in their area of expertise often search for a predetermined  type of structure, or for structures exhibiting characteristics specic to the domain.  This paper presents methods for guiding the discovery process with domain-specic  knowledge. In this paper, the Subdue discovery system is used to evaluate the bene-  ts of using domain knowledge. The domain knowledge is incorporated into Subdue  following a single general methodology to guide the discovery process. Results show  using domain-specic knowledge improves the search for substructures which are useful  to the domain, and leads to greater compression of the data. To illustrate these bene-  ts, examples and experiments from the domain of computer programming, computer  aided design circuit, and a series of articially-generated domains...
Knowledge Discovery from Structural Data.
Discovering repetitive substructure in a structural database improves the ability to interpret and compress the data. This paper describes the Subdue system that uses domain-independent and domain-dependent heuristics to find interesting and repetitive structures in structural data. This substructure discovery technique can be used to discover fuzzy concepts, compress the data description, and formulate hierarchical substructure definitions. Examples from the domains of scene analysis, chemical compound analysis, computer-aided design, and program analysis demonstrate the benefits of the discovery technique. 1 Introduction  The large amount of data collected today is quickly overwhelming researchers&#039; abilities to interpret the data and discover interesting patterns within the data. In response to this problem, a number of researchers have developed techniques for discovering concepts in databases [2, 5, 15]. These techniques work well for data expressed in a non-structural, attribute-v...
An Empirical Approach to Solving the General Utility Problem in Speedup Learning.
Many recent approaches to avoiding the utility problem in speedup learning (the eventual degradation of performance due to increasing amounts of learned problem-solver control knowledge) rely on sophisticated utility measures and significant numbers of training problems to accurately estimate the utility of control knowledge. Empirical results presented here and elsewhere indicate that a simple selection strategy of retaining all control rules derived from a training problem solution quickly defines an efficient set of control knowledge from few training problems. This simple selection strategy provides a low-cost alternative to example-intensive approaches for improving the speed of a problem solver. Experimentation illustrates the existence of a minimum (representing least cost) in the learning curve which is reached after a few training examples. Stress is placed on controlling the amount of learned knowledge as opposed to which knowledge. An attempt is also made to relate domain ch...
Substucture Discovery in the SUBDUE System.

Substructure Discovery Using Minimum Description Length and Background Knowledge
The ability to identify interesting and repetitive substructures is an essential component to discovering knowledge in structural data. We describe a new version of our Subdue  substructure discovery system based on the minimum description length principle. The Subdue system discovers substructures that compress the original data and represent structural concepts in the data. By replacing previously-discovered substructures in the data, multiple passes of Subdue produce a hierarchical description of the structural regularities in the data. Subdue uses a computationally-bounded inexact graph match that identifies similar, but not identical, instances of a substructure and finds an approximate measure of closeness of two substructures when under computational constraints. In addition to the minimum description length principle, other background knowledge can be used by Subdue to guide the search towards more appropriate substructures. Experiments in a variety of domains demonstrate Subdu...
Substructure Discovery Using Minimum Description Length and Background Knowledge.
The ability to identify interesting and repetitive substructures is an essential component to discovering knowledge in structural data. We describe a new version of our Subdue  substructure discovery system based on the minimum description length principle. The Subdue system discovers substructures that compress the original data and represent structural concepts in the data. By replacing previously-discovered substructures in the data, multiple passes of Subdue produce a hierarchical description of the structural regularities in the data. Subdue uses a computationally-bounded inexact graph match that identifies similar, but not identical, instances of a substructure and finds an approximate measure of closeness of two substructures when under computational constraints. In addition to the minimum description length principle, other background knowledge can be used by Subdue to guide the search towards more appropriate substructures. Experiments in a variety of domains demonstrate Subdu...
Discovery of Inexact Concepts from Structural Data.
Introduction  Automated knowledge discovery is essential for extracting information from databases [2]. However, complex databases have moved from the simplistic attribute-value representation assumed by recent knowledge-discovery systems to a structural data representation that reflects the relationships among objects. Discovering concepts in this structural data requires the identification of common substructures within the data. The motivation for this process is not merely to find substructures capable of compressing the data by abstracting instances of the substructure, but also to identify conceptually interesting substructures that enhance the interpretation of the data. Substructure discovery is the process of identifying concepts describing interesting and repetitive substructures within structural data. Once discovered, the substructure concept can be used to simplify the data by replacing instances of the substructure with a pointer to the newly discovered concept. T
Empirical Analysis of the General Utility Problem in Machine Learning.
The overfit problem in inductive learning and the utility problem in speedup learning both describe a common behavior of machine learning methods: the eventual degradation of performance due to increasing amounts of learned knowledge. Plotting the performance of the changing knowledge during execution of a learning method (the performance response) reveals similar curves for several methods. The performance response generally indicates an increase to a single peak followed by a more gradual decrease in performance. The similarity in performance responses suggests a model relating performance to the amount of learned knowledge. This paper provides empirical evidence for the existence of a general model by plotting the performance responses of several learning programs. Formal models of the performance response are also discussed. These models can be used to control the amount of learning and avoid degradation of performance.  Introduction  As machine learning methods acquire increasing ...
Towards Intelligent Machine Learning Algorithms.

Fuzzy Substructure Discovery.
This paper describes a method for discovering substructures in data using a fuzzy graph match. A previous implementation of the Subdue system discovers substructures based on the psychologically-motivated criteria of cognitive savings, compactness, connectivity and coverage. However, the instances in the data must exactly match the discovered substructures. We describe a new implementation of Subdue that employs a fuzzy graph match to discover substructures which occur often in the data, but not always in the same form. This fuzzy substructure discovery can be used to formulate fuzzy concepts, compress the data description, and discover interesting structures in data that are found either in their pure form or in a slightly convoluted form. Examples from the domains of scene analysis and chemical compound analysis demonstrate the fuzzy discovery technique.  1 INTRODUCTION  Substructure discovery is the process of identifying concepts describing interesting and repetitive &#034;chunks&#034; of st...
Application of Machine Learning to the Maintenance of Knowledge%2DBased Performance.
Development of expert systems involves knowledge acquisition which can be supported by applying machine learning techniques. This paper presents the basic idea of using decision-tree induction in process optimization and development of the domain model of electrochemical machining (ECM). It further discusses how decision-tree induction is used to build and refine the knowledge base of the process. The idea of developing an intelligent supervisory system with a learning component (IMAFO, Intelligent MAnufacturing FOreman) that is already implemented, is briefly introduced. The results of applying IMAFO for analyzing data form the ECM process are presented. How the domain model of the process (electrochemical machining) is built from the initial known information and how the results of decision-tree induction can be used to optimize the model of the process and further refine the knowledge base are shown. Two examples are given to demonstrate how new rules (to be included in the knowledg...
The General Utility Problem in Machine Learning.
The overfit problem in inductive learning and the utility problem in speedup learning both describe a common behavior of machine learning methods: the eventual degradation of performance due to increasing amounts of learned knowledge. Plotting the performance of the changing knowledge during execution of a learning method (the performance response) reveals similar curves for several methods. The performance response generally indicates an increase to a single peak followed by a more gradual decrease in performance. The similarity in performance responses suggests a model relating performance to the amount of learned knowledge. This paper provides empirical evidence for the existence of a general model by plotting the performance responses of several learning programs. Formal models of the performance response are also discussed. These models can be used to control the amount of learning and avoid degradation of performance.  Introduction  As machine learning methods acquire increasing ...
Accelerated learning on the connection machine.
The complexity of most machine learning techniques can be improved by transforming iterative components into their parallel equivalent. Although this parallelization has been considered in theory, few implementations have been performed on existing parallel machines. The parallel architecture of the Connection Machine provides a platform for the implementation and evaluation of parallel learning techniques. The architecture of the Connection Machine is described along with limitations of the language interface that constrain the implementation of learning programs. Connection Machine implementations of two learning programs, Perceptron and AQ, are described, and their computational complexity is compared to that of the corresponding sequential versions using actual runs on the Connection Machine. Techniques for parallelizing ID3 are also analyzed, and the advantages and disadvantages of parallel implementation on the Connection Machine are discussed in the context of machine learning. ...
Empirical Substructure Discovery.

Towards Intelligent Machine Learning Algorithms.

